package com.shm.leetcode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 786. 第 K 个最小的素数分数
 * 给你一个按递增顺序排序的数组 arr 和一个整数 k 。数组 arr 由 1 和若干 素数  组成，且其中所有整数互不相同。
 *
 * 对于每对满足 0 < i < j < arr.length 的 i 和 j ，可以得到分数 arr[i] / arr[j] 。
 *
 * 那么第 k 个最小的分数是多少呢?  以长度为 2 的整数数组返回你的答案, 这里 answer[0] == arr[i] 且 answer[1] == arr[j] 。
 *
 *
 * 示例 1：
 *
 * 输入：arr = [1,2,3,5], k = 3
 * 输出：[2,5]
 * 解释：已构造好的分数,排序后如下所示:
 * 1/5, 1/3, 2/5, 1/2, 3/5, 2/3
 * 很明显第三个最小的分数是 2/5
 * 示例 2：
 *
 * 输入：arr = [1,7], k = 1
 * 输出：[1,7]
 *
 *
 * 提示：
 *
 * 2 <= arr.length <= 1000
 * 1 <= arr[i] <= 3 * 104
 * arr[0] == 1
 * arr[i] 是一个 素数 ，i > 0
 * arr 中的所有数字 互不相同 ，且按 严格递增 排序
 * 1 <= k <= arr.length * (arr.length - 1) / 2
 * @author SHM
 */
public class KthSmallestPrimeFraction {
    /**
     * 方法一：自定义排序
     * 思路与算法
     *
     * 记数组 \textit{arr}arr 的长度为 nn。我们可以将全部的 \dfrac{n(n-1)}{2}
     * 2
     * n(n−1)
     * ​
     *   个分数放入数组中进行自定义排序，规则为将这些分数按照升序进行排序。
     *
     * 在排序完成后，我们就可以得到第 kk 个最小的素数分数。
     *
     * 细节
     *
     * 当我们比较两个分数 \dfrac{a}{b}
     * b
     * a
     * ​
     *   和 \dfrac{c}{d}
     * d
     * c
     * ​
     *   时，我们可以直接对它们的值进行比较，但这会产生浮点数的计算，降低程序的效率，并且可能会引入浮点数误差。一种可行的替代方法是用：
     *
     * a \times d < b \times c
     * a×d<b×c
     *
     * 来替代 \dfrac{a}{b} < \dfrac{c}{d}
     * b
     * a
     * ​
     *  <
     * d
     * c
     * ​
     *   的判断，二者是等价的。
     *   复杂度分析
     *
     * 时间复杂度：O(n^2 \log n)O(n
     * 2
     *  logn)，其中 nn 是数组 \textit{arr}arr 的长度。素数分数一共有 \dfrac{n(n-1)}{2} = O(n^2)
     * 2
     * n(n−1)
     * ​
     *  =O(n
     * 2
     *  ) 个，因此排序需要的时间为 O(n^2 \log n)O(n
     * 2
     *  logn)。
     *
     * 空间复杂度：O(n^2)O(n
     * 2
     *  )，即为存储所有素数分数需要的空间。
     *
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/k-th-smallest-prime-fraction/solution/di-k-ge-zui-xiao-de-su-shu-fen-shu-by-le-argw/
     *
     * @param arr
     * @param k
     * @return
     */
    public int[] kthSmallestPrimeFraction(int[] arr, int k) {
        int n = arr.length;
        List<int[]> list = new ArrayList<>();
        for (int i = 0; i < n-1; i++) {
            for (int j = i+1; j < n; j++) {
                list.add(new int[]{arr[i],arr[j]});
            }
        }
        Collections.sort(list,(x,y)->x[0]*y[1]-x[1]*y[0]);
        return list.get(k-1);
    }
}
